import java.util.Arrays;

public class Solution1 {

    public static void main(String[] args) {
        Solution1 solution1 = new Solution1();
        int[] nums = {10,9,2,5,3,7,101,18};
        System.out.println(solution1.lengthOfLIS(nums));
    }
    // 解法一：递归
    public int lengthOfLIS(int[] nums) {
        int ret = 0;
        int n = nums.length;

        for(int i = 0; i < n; i++) {
            ret = Math.max(ret,dfs(i, nums));
        }
        return ret;
    }

    public int dfs(int pos, int[] nums) {
        int ret = 1;
        for(int i = pos + 1; i < nums.length; i++) {
            if(nums[i] > nums[pos]) {
                ret = Math.max(ret, dfs(i, nums) + 1);
            }
        }
        return ret;
    }

    // 解法二：记忆化搜索
    public int lengthOfLIS1(int[] nums) {
        int ret = 0;
        int n = nums.length;
        int[] memo = new int[n];

        for(int i = 0; i < n; i++) {
            ret = Math.max(ret,dfs1(i, nums, memo));
        }
        return ret;
    }

    public int dfs1(int pos, int[] nums, int[] memo) {
        if(memo[pos] != 0) {
            return memo[pos];
        }
        int ret = 1;
        for(int i = pos + 1; i < nums.length; i++) {
            if(nums[i] > nums[pos]) {
                ret = Math.max(ret, dfs1(i, nums, memo) + 1);
            }
        }
        return ret;
    }

    // 解法三：动态规划
    public int lengthOfLIS2(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int ret = 0;
        Arrays.fill(dp, 1);
        // 填表顺序 : 从后往前
        for(int i = n -1; i >= 0; i--) {
            for(int j = i + 1; j < n; j++) {
                if(nums[j] > nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ret = Math.max(ret, dp[i]);
        }
        return ret;

    }
}
